package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.StackProblem;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * @author tzp
 * @since 2020/10/17
 */
public class LC739 implements StackProblem {
    //how many days you would have to wait until a warmer temperature
    public int[] dailyTemperatures(int[] T) {
        if (T == null || T.length == 0) return null;
        LinkedList<Integer> list = new LinkedList<>();
        int[] result = new int[T.length];

        for (int i = T.length - 1; i >= 0; i--) {
            while (list.size() > 0 && T[list.peekLast()] <= T[i]) {
                list.pollLast();
            }
            if (list.size() > 0) result[i] = list.peekLast() - i;
            list.offerLast(i);
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new LC739()
                //1, 1, 4, 2, 1, 1, 0, 0
                .dailyTemperatures(new int[]{73, 74, 75, 71, 69, 72, 76, 73})));

    }
}
